package com.yeung.swordoffer;

/**
 * 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
 */
public class 对称的二叉树 {
    /**
     * 【分析1】首先我们需要明确一下镜像二叉树的概念，简单来说就是左子树与右子树对调。
     * 而根据树的递归定义可以，左子树和右子树的定义也是递归而言的。
     * <p>
     * 【分析2】接下来我们需要明确两棵二叉树什么时候相同。显然，根结点的值相等，左右子树相同，则这两颗二叉树相同。
     * 显然，在判断两棵二叉树是否相同时也需要递归地进行判断。
     * <p>
     * 【分析3】题目中并不是想让我们判断任意两棵二叉树是否相同，而是要求我们判断一棵二叉树和它的镜像二叉树是否相同。
     * 因此我们判断相同的条件不就很明显的变成了：根结点对应的值相等，原二叉树Root的左子树与其镜像二叉树Root'的右子树相同，
     * 且原二叉树Root的右子树与其镜像二叉树Root'的左子树相同。如此递归下去。直到① 如果Root和Root'均为空，则返回true；
     * ② 如果Root为空或者Root'为空，则返回false；③ 如果Root对应的值与Root'对应的值不相等，则返回false。
     * ————————————————
     *
     * @param pRoot
     * @return
     */
    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) return true;
        return judge(pRoot, pRoot);
    }

    boolean judge(TreeNode pRoot, TreeNode cRoot) {
        if (pRoot == null & cRoot == null) return true;

        if (pRoot == null || cRoot == null)
            //有一个为空 那么不等
            return false;

        if (pRoot.val != cRoot.val)
            return false;
        //镜像要相等
        return judge(cRoot.left, pRoot.right) && judge(pRoot.right, cRoot.left);
    }
}
